package leetcode.all;

/**
 * 按成绩分糖果，如果比两侧成绩好要分到更多糖果，问这么一列孩子至少需要多少糖果
 */

public class Solution135 {

    public int candy(int[] ratings) {

        int n = ratings.length;
        int[] left = new int[n]; //从左向右看
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = ratings[i]>ratings[i-1]?left[i-1]+1:1;
        }
        int[] right = new int[n]; //从右向左看
        right[n-1] = 1;
        for (int i = n-2; i >=0; i--) {
            right[i] = ratings[i]>ratings[i+1]?right[i+1]+1:1;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += Math.max(left[i],right[i]);
        }
        return count;
    }
}
